package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ48 从单向链表中删除指定值的节点   链表
 * @Date: created in 2024/12/31 星期二 11:21
 * @Modified By:
 */
public class HJ48_RemoveNodeWithSpecifiedValue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // 获取链表的节点数量
            int n = in.nextInt();
            // 获取链表的头节点
            int h = in.nextInt();

            // 构建链表, 头节点已经加进去了, 所以循环数为 n - 1
            LinkedList linkedList = new LinkedList(h);
            for (int i = 0; i < n - 1; i++) {
                int val = in.nextInt();
                int node = in.nextInt();
                linkedList.insert(val, node);
            }

            // 删除指定的节点
            int k = in.nextInt();
            linkedList.delete(k);

            // 打印
            ListNode p = linkedList.head;
            while (p != null && p != linkedList.dummyTail) {
                System.out.print(p.val + " ");
                p = p.next;
            }
        }
    }

    // 链表类
    public static class LinkedList {
        public ListNode head;

        // 虚拟头节点
        public ListNode dummyHead;

        // 虚拟尾节点
        public ListNode dummyTail;

        public LinkedList(int val) {
            dummyHead = new ListNode(0);
            dummyTail = new ListNode(0);
            head = new ListNode(val, dummyHead, dummyTail);
            dummyHead.next = head;
            dummyTail.pre = head;
        }

        // 新增节点, 按指定的node后面添加节点
        public void insert(int val, int node) {
            ListNode p = dummyHead.next;

            while (p.val != node) {
                p = p.next;
            }
            // 遍历到虚拟尾节点, 说明没有指定的node, 直接返回
            if (p == dummyTail) {
                return;
            }
            // 新增节点的上一节点
            ListNode pre = p;
            // 新增节点的下一节点
            ListNode next = p.next;

            // 新节点创建, 维护指针
            ListNode newNode = new ListNode(val, pre, next);
            pre.next = newNode;
            next.pre = newNode;
        }

        // 删除指定的节点
        public void delete(int node) {
            ListNode p = dummyHead.next;

            while (p.val != node) {
                p = p.next;
            }

            // 遍历到虚拟尾节点, 说明没有指定的node, 直接返回
            if (p == dummyTail) {
                return;
            }

            // 待删除节点的上一节点
            ListNode pre = p.pre;
            // 待删除节点的下一节点
            ListNode next = p.next;

            // 维护指针
            pre.next = next;
            next.pre = pre;

            // 清除待删除节点与其下一节点的关系
            p.next = null;
            p.pre = null;
        }
    }

    // 节点类
    public static class ListNode {
        public int val;

        public ListNode pre;

        public ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode pre, ListNode next) {
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    }
}
